#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=140 lang=cpp
 *
 * [140] 单词拆分 II
 */

// @lc code=start
class Solution {
public:
    vector<string> res;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> exists;
        for (int i = 0; i < wordDict.size(); i++) exists.insert(wordDict[i]);
        dfs("", exists, 0, s);
        return res;
    }

    void dfs(string now, unordered_set<string> & exists, int index, const string & input) {
        if (index >= input.size()) {
            now.pop_back();
            res.push_back(now);
            return;
        }
        // e - i + 1 = num
        for (int i = index; i < input.size(); i++) {
            string x = input.substr(index, i - index + 1);
            if (exists.count(x)) {
                string m = now;
                m.append(x); m.push_back(' ');
                dfs(m, exists, i + 1, input);
            }
        }
    }
};
// @lc code=end

